package com.ShangGuiGu.Tree;

import lombok.Data;

/**
 * @authoer zsj
 * @date 2022/3/6 15:57
 * <p>
 * <p>
 * 二叉树
 * 每个父节点最多只有两个子节点的树叫二叉树
 * <p>
 * 前序遍历，中序遍历，后序遍历
 * <p>
 * 前序遍历:父节点-左节点-右节点
 * 中序遍历:左节点-父节点-右节点
 * 后序遍历:左节点-右节点-父节点
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        Node root = new Node(1,"one");
        Node node2 = new Node(2,"two");
        Node node3 = new Node(3,"three");
        Node node4 = new Node(4,"four");
        Node node5 = new Node(5,"five");
        BinaryTree binaryTree = new BinaryTree(root);
        //创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        //前序遍历
        System.out.println("pre");
        binaryTree.preOrder();

        //中序遍历
        System.out.println("infix");
        binaryTree.infixOrder();

        //后序遍历
        System.out.println("after");
        binaryTree.afterOrder();
    }

}

@Data
class BinaryTree {
    private Node root;//根节点

    public BinaryTree(Node root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            //如果根节点不为空，也就是树不为空时开始前序遍历
            this.root.preOrder();
        } else {
            System.out.println("Binary TreeNode is null,please insert some data for try again");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("Binary TreeNode is null,please insert some data for try again");
        }
    }

    //后序遍历
    public void afterOrder() {
        if (this.root != null) {
            this.root.afterOrder();
        } else {
            System.out.println("Binary TreeNode is null,please insert some data for try again");
        }
    }

}

/**
 * 节点类
 * 每一个节点都有或者没有它的数据和子节点
 */
@Data
class Node {
    int no;
    String data;
    //左右节点默认为空
    private Node left;
    private Node right;

    public Node(int no, String data) {
        super();
        this.no = no;
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", data='" + data + '\'' +
                '}';
    }

    //编写前序遍历
    public void preOrder() {
        System.out.println(this);//输出父节点
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右子树遍历
        if (this.right != null) {
            this.right.preOrder();
        }

    }

    //中序遍历
    public void infixOrder() {
        //递归向左节点遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //输出节点
        System.out.println(this);
        //递归向右节点遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //后序遍历
    public void afterOrder() {
        if (this.left != null) {
            //递归寻找左节点
            this.left.afterOrder();
        }
        if (this.right != null) {
            //递归往下遍历右节点
            this.right.afterOrder();
        }
        //输出当前节点
        System.out.println(this);
    }
}
